package challenge01;

import java.util.*;

/**
 * @author DCSGO
 * @version 1.0
 */

/*
选课组合
大学选课可以选择不同的课程。小许本学期计划选修K门课程且希望学分尽可能多。由于有些课程的关系密切，
这些课程构成一个课程包（课程包的课程必须同时选，同一门课程不会在不同的课程包中同时出现）。假定
这学期有N门课程，其中包括M个课程包，各课程的上课时间相互不冲突，请帮他选择K门课程可以获得的最高总学分。
输入说明：第一行是三个整数N（3<=N<=50），M（1<=M<=50）和K（1<=K<=10），之后是N行，每行包括课程
的编号（非0开始的4位数字编码）、课程的学分，中间用空格隔开；之后M行是课程包信息，每行包括多门课程编号，以0结束。
输出说明：输出可获得的最高总学分（精确到小数点后1位）。
 */
/*
输入样例：
5  1  3
2503  2.5
2701  3.0
2301  2.5
2702  1.0
2506  2.0
2701  2702 0

输出样例：
7.0

10  3  7
2503  2.5
2701  3.0
2301  2.5
2702  1.0
2506  2.0
2001  3.1
2008  4.2
2002  0.5
1001  2.3
1031  3.1
2701  2702 0
2008  1001 2002 0
1031  2001 2503 0

*/
/* 分析：
 * 1.要选择k门课程
 * 2.每个课程包中有x门课程
 * 3.课程包中的课程必须同时选
 * 也就是说，选择课程要以课程包为单位，每选择一个课程包都会使还能继续选择的课程数减少(课程包中课程的个数)，
 * 同时也会获得该课程包中的所有课程的学分；每个课程包只有选和不选。
 * 暴力尝试，通过递归求解，递归函数解决所有课程包中刚好使得课程总数等于k并返回能够获得的最大学分是多少
 */

class Course {
    int id;
    double credit;

    Course(int id, double credit) {
        this.id = id;
        this.credit = credit;
    }

    @Override
    public String toString() {
        return id + " " + credit;
    }
}

public class P3 {
    /**
     * @param packSums     各个课程包的学分
     * @param packCounts   各个课程包有多少门课
     * @param curPackIndex 当前选择到的课程包的下标
     * @param k            需要选择的课程数
     * @return 选择k门课程能获取的最大学分
     */
    public static double getMaxCredit(ArrayList<Double> packSums, ArrayList<Integer> packCounts,
                                      int curPackIndex, int k) {
        //System.out.println("进入递归 i = " + curPackIndex + " k = " + k);
        //需要选择的课程数为<=0 或 没有能选的课课程包了
        if (k <= 0 || curPackIndex >= packSums.size()) {
            //System.out.println("return 0 结束递归 i = " + curPackIndex + " k = " + k);
            return 0;//直接返回0
        }
        //选择课程包 当前课程包的学分 + 后续能获取的最大学分
        //选择了当前课程包所以后续需要选择的课程k需要减去当前课程包中的课程数
        double credit1 = 0;
        //必须要求选择当前课程包后需要选择的课程数不为负数 不然会选课会超过k
        if (k - packCounts.get(curPackIndex) >= 0) {
            credit1 = packSums.get(curPackIndex) + getMaxCredit(packSums, packCounts,
                    curPackIndex + 1, k - packCounts.get(curPackIndex));
        }
        //System.out.println("计算credit1 = " + credit1 + " i = " + curPackIndex + " k = " + k);
        //不选择当前课程包 后续能获取的最大学分
        double credit2 = getMaxCredit(packSums, packCounts,
                curPackIndex + 1, k);
        //System.out.println("计算credit2 = " + credit2 + " i = " + curPackIndex + " k = " + k);
        //最大学分为选择当前课程包与不选择当前课程包的最大值
        double ans = Math.max(credit1, credit2);
        //System.out.println("结束递归 ans = " + ans);
        return ans;
    }
    //递归改dp1
    public static double getMaxCreditDP(ArrayList<Double> packSums, ArrayList<Integer> packCounts, int k) {
        int maxRows = k + 1;
        int maxCols = packSums.size() + 1;
        double[][] ans = new double[maxRows][maxCols];
        //初始化第一行
        for (int i = 0; i < maxCols; i++) {
            ans[0][i] = 0;
        }
        //初始化最后一列
        for (int j = 0; j < maxRows; j++) {
            ans[j][maxCols - 1] = 0;
        }
        for (int j = 1; j < maxRows; j++) {
            for (int i = maxCols - 2; i >= 0; i--) {
                if (j - packCounts.get(i) >= 0) {
                    ans[j][i] = Math.max(packSums.get(i) + ans[j - packCounts.get(i)][i + 1], ans[j][i + 1]);
                } else {
                    ans[j][i] = ans[j][i + 1];
                }
            }
        }
        return ans[maxRows - 1][0];
    }
    //递归改dp2 添加了注释 还可以进一步优化成一维数组
    public static double getMaxCreditDP2(ArrayList<Double> packSums, ArrayList<Integer> packCounts, int k) {
        int maxRows = k + 1;//行数
        int maxCols = packSums.size() + 1;//列数
        //ans 的行表示需要选修的课程数 列表示课程包下标
        double[][] ans = new double[maxRows][maxCols];
        //初始化第一行 选修课程数为0 后续能得到的学分为0
        for (int j = 0; j < maxCols; j++) {
            ans[0][j] = 0;
        }
        //初始化最后一列 没有可选的课程包了 后续能得到的学分为0
        for (int i = 0; i < maxRows; i++) {
            ans[i][maxCols - 1] = 0;
        }
        for (int i = 1; i < maxRows; i++) {//需要选修的课程数
            for (int j = maxCols - 2; j >= 0; j--) {//课程包下标
                if (i - packCounts.get(j) >= 0) {//选择当前课程包不会超出总选课数i
                    //需要选修i门课程并在选择j课程包时的最大学分等于 选择该课程包与不选择该课程包的最大学分
                    //选择该课程包的最大学分=该课程包的学分+先前选修(i - packCounts.get(j))门课程的最大学分
                    //不选择该课程包的最大学分=先前选修i门课程的最大学分
                    ans[i][j] = Math.max(packSums.get(j) + ans[i - packCounts.get(j)][j + 1], ans[i][j + 1]);
                } else {//不能选择该选课包最大学分只能是先前选修k=i门课程的最大学分
                    ans[i][j] = ans[i][j + 1];
                }
            }
        }
        //选修K门课程的最大学分 列为0是因为课程包是倒序遍历的
        //求解到最后一个课程包才获得了最终解
        return ans[maxRows - 1][0];
    }

    public static void main(String[] args) {
        int N, M, K;
        HashMap<Integer, Course> courses = new HashMap<>();
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();
//        System.out.println(N);
//        System.out.println(M);
//        System.out.println(K);
        for (int i = 0; i < N; i++) {
            int id = scanner.nextInt();
            double credit = scanner.nextDouble();
            courses.put(id, new Course(id, credit));
        }
//        Collection<Course> values = courses.values();
//        for (Course course : values) {
//            System.out.println(course);
//        }
        ArrayList<Double> packSums = new ArrayList<>();
        ArrayList<Integer> packCounts = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            double curPackSum = 0;
            int curPackCount = 0;
            while (scanner.hasNext()) {
                int id = scanner.nextInt();
                if (id != 0) {//计算课程包中的学分
                    curPackSum += courses.remove(id).credit;
                    curPackCount++;
                } else {
                    break;
                }
            }
            packSums.add(curPackSum);
            packCounts.add(curPackCount);
        }
        Collection<Course> residueCourse = courses.values();
        for (Course rc : residueCourse) {
            packSums.add(rc.credit);
            packCounts.add(1);
        }
        System.out.println("各个课程包的学分：" + packSums);
        System.out.println("各个课程包的课程数量：" + packCounts);
        double maxCredit = getMaxCredit(packSums, packCounts, 0, K);
        double maxCredit2 = getMaxCreditDP(packSums, packCounts, K);
        double maxCredit3 = getMaxCreditDP2(packSums, packCounts, K);
        System.out.println(maxCredit);
        System.out.println(maxCredit2);
        System.out.println(maxCredit3);
        /* 测试样例1
         * 5  1  3
         * 2503  2.5
         * 2701  3.0
         * 2301  2.5
         * 2702  1.0
         * 2506  2.0
         * 2701  2702 0
         * 各个课程包的学分：[4.0, 2.5, 2.0, 2.5]
         * 各个课程包的课程数量：[2, 1, 1, 1]
         * 7.0
         * 7.0
         * 7.0
         *
         * 进程已结束，退出代码为 0
         */

        /* 测试样例2
         * 10  3  7
         * 2503  2.5
         * 2701  3.0
         * 2301  2.5
         * 2702  1.0
         * 2506  2.0
         * 2001  3.1
         * 2008  4.2
         * 2002  0.5
         * 1001  2.3
         * 1031  3.1
         * 2701  2702 0
         * 2008  1001 2002 0
         * 1031  2001 2503 0
         * 各个课程包的学分：[4.0, 7.0, 8.7, 2.0, 2.5]
         * 各个课程包的课程数量：[2, 3, 3, 1, 1]
         * 18.2
         * 18.2
         * 18.2
         *
         * 进程已结束，退出代码为 0
         */
    }
}
